package 代码随想2._1数组;

/**
 * @author XXX
 * @date 2024-01-13 19:27
 */

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/minimum-size-subarray-sum/description/
 * 滑动窗口
 */
public class _4长度最小的子数组 {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int res = Integer.MAX_VALUE;
        for(int right = 0; right < nums.length; right++){
            sum+=nums[right];
            while (sum>=target){
                res = Math.min(res,right-left+1);
                sum-=nums[left++];
            }
        }
        return res == Integer.MAX_VALUE?0:res;
    }
}

/**
 * https://leetcode.cn/problems/fruit-into-baskets/description/
 */
class 水果成篮{
    public int totalFruit(int[] fruits) {
        Map<Integer,Integer> cnt = new HashMap<>();
        int left = 0 , ans = 0;
        for(int right=0; right<fruits.length;right++){
            cnt.put(fruits[right],cnt.getOrDefault(fruits[right],0)+1);
            while (cnt.size()>2){
                cnt.put(fruits[left],cnt.get(fruits[left]) - 1);
                if(cnt.get(fruits[left])==0)
                    cnt.remove(fruits[left]);
                ++left;
            }
            ans = Math.max(ans, right-left+1);
        }
        return ans;
    }
}


/**
 * https://leetcode.cn/problems/minimum-window-substring/description/
 */
class 最小覆盖子串{
    public String minWindow(String s, String t) {
        Map<Character,Integer> need = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
        }
        int right = 0, left = 0;
        int valid = 0;
        int start = 0, minLen = Integer.MAX_VALUE;

        while (right < s.length()) {
            char cur = s.charAt(right);
            right++;
            // 进行窗口数据一系列更新
            if (need.containsKey(cur)) {
                window.put(cur,window.getOrDefault(cur, 0)+1);
                if (window.get(cur).equals(need.get(cur))) {
                    valid++;
                }
            }
            while (need.size() == valid) {
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }
                // d 是将移除窗口的字符串
                char d = s.charAt(left);
                // 左边移动窗口
                left++;
                // 进行窗口内数据当一系列更新
                if (window.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start,start+minLen);
    }
}
